package edu.whu.rose.clock.kps.algorithm.sortedlists;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.TreeSet;

import com.sleepycat.je.DatabaseException;

import edu.whu.rose.clock.kps.algorithm.SearchAlgorithm;
import edu.whu.rose.clock.kps.datastruct.SimpleAnswer;
import edu.whu.rose.clock.kps.datastruct.SimpleMatchedSubgraph;
import edu.whu.rose.clock.kps.datastruct.SimpleSubgraphVertex;
import edu.whu.rose.clock.kps.spindex.ShortestPathIndexDB;
import edu.whu.rose.clock.ssql.graph.RRadiusSubGraph;
import edu.whu.rose.clock.ssql.subgraph.SubgraphDB;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;

public class SortedListSearch extends SearchAlgorithm {

	private int groupNum;
	private SimpleMatchedSubgraph[] matched_subgraphs;

	private ArrayList<TreeSet<ListItem>> sortedLists;

	private ShortestPathIndexDB disDB;
	private ShortestPathIndexDB preDB;
	private SubgraphDB sgdb;
	
	private HashMap<Integer, int[]> allVertexes;
	private HashMap<Integer, HashMap<Integer, int[]>> allPredecessors;

	public SortedListSearch(int groupNum,
			SimpleMatchedSubgraph[] matched_subgraphs,
			ShortestPathIndexDB disDB, ShortestPathIndexDB preDB,
			SubgraphDB sgdb) {
		this.groupNum = groupNum;
		this.matched_subgraphs = matched_subgraphs;
		sortedLists = new ArrayList<TreeSet<ListItem>>();
		for (int i = 0; i < groupNum; i++) {
			sortedLists.add(new TreeSet<ListItem>());
		}
		this.disDB = disDB;
		this.preDB = preDB;
		this.sgdb = sgdb;
		
		allVertexes = new HashMap<Integer, int[]>();
		allPredecessors = new HashMap<Integer, HashMap<Integer, int[]>>();
	}

	public void init() {
		for (int i = 0; i < matched_subgraphs.length; i++) {
			SimpleMatchedSubgraph sms = matched_subgraphs[i];
			int subgraph = sms.getSubgraphID();
			RRadiusSubGraph rrsg = null;
			try {
				rrsg = sgdb.getSubGraph(subgraph);
				allVertexes.put(new Integer(subgraph), rrsg.getVertexes());
			} catch (DatabaseException ex) {
				ex.printStackTrace();
			}
			for (int j = 0; j < groupNum; j++) {
				int[] group = sms.getGroup(j);
				for (int k = 0; k < group.length; k++) {
					int vertex = group[k];
					int[] distances = null;
					try {
						distances = disDB.search(subgraph, vertex);
					} catch (DatabaseException ex) {
						ex.printStackTrace();
					}
					int[] vertexes = rrsg.getVertexes();
					if (vertexes.length != distances.length) {
						System.err
								.println("Error: dismatched length of vertexes and distances in subgraph: "
										+ subgraph);
					}
//					int vPosition = Arrays.binarySearch(vertexes, vertex);
					for (int l = 0; l < vertexes.length; l++) {
						ListItem li = new ListItem(distances[l], subgraph,
								vertex, vertexes[l], l);
						sortedLists.get(j).add(li);
					}
				}
			}
		}
	}

	public SimpleAnswer[] process(int k) {
		ConnectedTree[] topk = new ConnectedTree[k];

		ArrayList<Iterator<ListItem>> its = new ArrayList<Iterator<ListItem>>();
		ArrayList<HashSet<SimpleSubgraphVertex>> roots = new ArrayList<HashSet<SimpleSubgraphVertex>>(
				groupNum);
		for (int i = 0; i < groupNum; i++) {
			its.add(sortedLists.get(i).iterator());
			roots.add(new HashSet<SimpleSubgraphVertex>());
		}

		HashSet<ListItem> items = new HashSet<ListItem>();
		int num = 0;
		while (num < k) {
			ListItem[] newItems = new ListItem[groupNum];
			for (int i = 0; i < groupNum; i++) {
				if (its.get(i).hasNext()) {
					newItems[i] = its.get(i).next();
				}
				roots.get(i).add(
						new SimpleSubgraphVertex(newItems[i]
								.getMatchedSubgraph(), newItems[i].getRoot()));
				items.add(newItems[i]);
			}
			for (int i = 0; i < groupNum; i++) {
				ListItem item = newItems[i];
				SimpleSubgraphVertex ssv = new SimpleSubgraphVertex(item
						.getMatchedSubgraph(), item.getRoot());
				boolean mark = true;
				for (int j = 0; j < groupNum; j++) {
					if (i != j) {
						if (!roots.get(j).contains(ssv)) {
							mark = false;
							break;
						}
					}
				}
				if (mark) {
					num++;
				}
				if (num >= k) {
					break;
				}
			}
		}

		Iterator<ListItem> it = items.iterator();
		while (it.hasNext()) {
			ListItem item = it.next();
			SequentialIntArray matchedVertexes = new SequentialIntArray();
			int score = 0;
			for (int i = 0; i < groupNum; i++) {
				Iterator<ListItem> it2 = sortedLists.get(i).iterator();
				while (it2.hasNext()) {
					ListItem item2 = it2.next();
					if (item.getMatchedSubgraph() == item2.getMatchedSubgraph()
							&& item.getRoot() == item2.getRoot()) {
						matchedVertexes.insert(item2.getMatchedVertex());
						score += item2.getDistance();
						break;
					}
				}
			}
			ConnectedTree ct = new ConnectedTree(item.getMatchedSubgraph(),
					item.getRoot(), item.getPosition(), matchedVertexes
							.getArray(), score);
			insertTree(topk, ct);
		}

		SimpleAnswer[] result = new SimpleAnswer[k];
		for (int i = 0; i < k; i++) {
			result[i] = genAnswer(topk[i].getSubgraph(), topk[i].getRoot(), topk[i].getPosition(), topk[i]
					.getMatched_vertexes());
		}

		return result;
	}

	private void insertTree(ConnectedTree[] topk, ConnectedTree ct) {
		int low = 0;
		int mid = 0;
		int top = topk.length - 1;
		while (low <= top) {
			mid = (low + top) / 2;
			if (topk[mid] == null || ct.getScore() < topk[mid].getScore()) {
				top = mid - 1;
			} else if (ct.getScore() > topk[mid].getScore()) {
				low = mid + 1;
			} else {
				for (int i = topk.length - 1; i > mid; i--) {
					topk[i] = topk[i - 1];
				}
				topk[mid] = ct;
				return;
			}
		}
		if (low < topk.length - 1) {
			for (int i = topk.length - 1; i > low; i--) {
				topk[i] = topk[i - 1];
			}
			topk[low] = ct;
		}
	}

	private SimpleAnswer genAnswer(int subgraph, int root, int position,
			int[] matched_vertexes) {
		int[] vertexes = allVertexes.get(new Integer(subgraph));
		int[][] paths = new int[matched_vertexes.length][];
		SequentialIntArray all = new SequentialIntArray();
		all.insert(root);
		for (int i = 0; i < matched_vertexes.length; i++) {
			int leaf = matched_vertexes[i];
			all.insert(leaf);
			int[] predecessors = getPredecessors(subgraph, leaf);
			ExpandableIntArray eia = new ExpandableIntArray();
			int current = position;
			int end = -1;
			for (int j = 0; j < predecessors.length; j++) {
				if (predecessors[j] == 0) {
					end = j;
					break;
				}
			}
			if (end == -1) {
				System.err.println("Error: invalid predecessors");
			}
			while (current != end) {
				current = predecessors[current] - 1;
				eia.add(current);
			}
			int[] path = new int[eia.getSize()];
			for (int j = 0; j < eia.getSize(); j++) {
				path[j] = vertexes[eia.get(eia.getSize() - j - 1)];
				all.insert(path[j]);
			}
			paths[i] = path;
		}
		
		return new SimpleAnswer(root, matched_vertexes, paths, all.getArray());
	}

	private int[] getPredecessors(int subgraph, int vertex) {
		int[] predecessors = null;
		HashMap<Integer, int[]> hm = allPredecessors.get(new Integer(subgraph));
		if (hm != null) {
			predecessors = hm.get(new Integer(vertex));
			if (predecessors != null) {
				return predecessors;
			}
			else {
				try {
					predecessors = preDB.search(subgraph, vertex);
				} catch (DatabaseException ex) {
					ex.printStackTrace();
				}
				return predecessors;
			}
		}
		else {
			try {
				predecessors = preDB.search(subgraph, vertex);
			} catch (DatabaseException ex) {
				ex.printStackTrace();
			}
			return predecessors;
		}
	}

}
